In order to reduce unnecessary update and solve the problem of low accuracy and poor stability of Label Propagation Algorithm (LPA), a Fast Label Propagation Algorithm based on Node Centrality and Community Similarity (FNCS_LPA) was proposed. According to the node centrality measure, the nodes of a network were sorted from low to high and added into node information list, which guided the update process to avoid unnecessary update and improve the stability of community detection. The accuracy of community detection was improved by a new update rule based on community similarity. Experiments were tested on a real social networks and LFR benchmarks. Compared with LPA and three improved LPA algorithms, the execution speed is improved by almost a dozen times, the modularities of the real social networks and the Normalized Mutual Information (NMI) of LFR (Lancichinetti Fortunato Radicchi) benchmark networks with more obscure community structure were significantly improved. The experimental results show that FNCS_LPA improves the accuracy and stability of community detection on the basis of improving execution speed.

In big data environment, the mass of nodes in graph and the complexity of analysis bring forward higher requirement for the speed and accuracy of maximum clique problems. In order to solve the problems, a Parallel Multi-layer Graph Partitioning method for Solving Maximum Clique (PMGP_SMC) was proposed. Firstly, a new Multi-layer Graph Partitioning method (MGP) was proposed, the large-scale graph partitioning was executed to generate subgraphs while the clique structure of the original graph was maintained and not destroyed. Large-scale subgraphs were divided into multi-level graphs to further reduce the size of subgraphs. The graph computing framework of GraphX was used to achieve MGP to form a Parallel Multi-layer Graph Partitioning (PMGP) method. Then, according to the size of partitioned subgraph, the iteration number of Local Search algorithm Based on Penalty value (PBLS) was reduced, and the PBLS based on Speed optimization (SPBLS) was proposed to solve the maximum clique of each subgraph. Finally, PMGP method and SPBLS were combined to form PMGP_SMC. The large-scale dataset of Stanford was used for running test. The experimental results show that, the proposed PMGP reduces the maximum subgraph size by more than 100 times and the average subgraph size by 2 times compared with Parallel Single Graph Partitioning method (PSGP). Compared with PSGP for Solving Maximum Clique (PSGP_SMC), the proposed PMGP_SMC reduces the overall time by about 100 times, and its accuracy is consistent with that of Parallel Multi-layer Graph Partitioning for solving maximum clique based on Maximal Clique Enumeration (PMGP_MCE) in solving the maximum clique. The proposed PMGP_SMC can solve the maximum clique of large-scale graph quickly and accurately.